package doing.doing_501_1000;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static java.lang.Math.max;

/**
 * 849. Maximize Distance to Closest Person 到最近的人的最大距离
 * <p>
 * 在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。
 * 至少有一个空座位，且至少有一人坐在座位上。
 * 亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。
 * 返回他到离他最近的人的最大距离。
 * <p>
 * 示例 1：
 * 输入：[1,0,0,0,1,0,1]
 * 输出：2
 * 解释：
 * 如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。
 * 如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。
 * 因此，他到离他最近的人的最大距离是 2 。
 * <p>
 * <p>
 * 我们也可以只用一次遍历，那么就需要在遍历的过程中统计出连续空位的个数，
 * 即连续0的个数。那么我们采用双指针来做，start 指向连续0的起点，初始化
 * 为0，i为当前遍历到的位置。遍历 seats 数组，跳过0的位置，当遇到1的时
 * 候，此时我们先判断下 start 的值，若是0的话，表明当前这段连续的空位是
 * 靠着墙的，所以我们要用连续空位的长度 i-start 来直接更新结果res，否则
 * 的话就是两头有人的中间的空位，那么用长度加1除以2来更新结果res，此时
 * start 要更新为 i+1，指向下一段连续空位的起始位置。for循环退出后，还是
 * 要处理最右边靠墙的位置，用 n-start 来更新结果res即可，
 *
 * @author 大硕
 * 2019-03-31 10:16 PM
 **/
@Slf4j
public class MaximizeDistanceToClosestPerson {

    @SuppressWarnings("all")
    public int maxDistToClosest(int[] seats) {
        int start = 0;
        int res = 0;
        for (int i = 0; i < seats.length; i++) {
            if (seats[i] != 1)
                continue;

            if (start == 0)
                res = max(res, i - start);
            else
                res = max(res, (i - start + 1) / 2);

            start = i + 1;
        }
        return max(res, seats.length - start);
    }

    @Test
    public void test() {
        log.info("{}", maxDistToClosest(new int[]{1, 0, 0, 0, 1, 0, 1}));
    }
}


































/*
public int maxDistToClosest(int[] seats) {
    int start = 0;
    int res = 0;
    for (int i = 0; i < seats.length; i++) {
        if (seats[i] != 1)
            continue;

        if (start == 0)
            res = max(res, i - start);
        else
            res = max(res, (i - start + 1) / 2);

        start = i + 1;
    }
    return max(res, seats.length - start);
}
*/
